package com.lw.leetcode.arr.a;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 42. 连续子数组的最大和
 * 面试题 16.17. 连续数列
 * 53. 最大子序和
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/26 9:12
 */
public class MaxSubArray {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int item = 0;
        for (int num : nums) {
            item += num;
            if (max < item) {
                max = item;
            }
            if (item < 0) {
                item = 0;
            }
        }
        return max;
    }

    public int maxSubArray2(int[] nums) {
        int max = nums[0];
        int sum = max;
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            if (sum < 0) {
                sum = nums[i];
            } else {
                if (sum + nums[i] <= 0) {
                    if (i < length - 1) {
                        sum = nums[++i];
                    }
                } else {
                    sum = sum + nums[i];
                }
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }

}
